1. Field of the invention
The present invention relates to a system employing a number of content-addressable memories accessed by a central processor, and more particularly to a processing system using a distributed associative (content addressable) memory consisting of separate content-addressable memory modules accessible over a serial communication link through corresponding sending modules which compress and transmit data according to content induced transaction overlap (CITO) methodology.
2. Description of the Background
Serial communication channels are commonly interconnected to multiple input/output ports which transfer data in accordance with the protocol of the communication channel. The data transferred on the bus is normally determined by the input/output port given access to the bus. Normally, one word or a sequence of words or a sequence of bits of a word may be transferred serially on the bus.
In U.S. Pat. No. 4,493,074, which issued on Jan. 8, 1985 to C. J. Walter, C. R. Wilson, and S. Berkovich, a communication channel was described incorporating a content induced transaction overlap (CITO) protocol. In the '074 patent, the senders simultaneously transmit the highest order bits of their data word one bit at a time serially and monitor the state of the communication channel. Transmission of data bits is terminated by all senders which detect a difference between the state of their transmitted data bit and the state of the communication channel. Bit competition performed at the end of each transmitted data word determines which sender has lexicographically the next smallest word from among those senders still having data bits remaining to be transmitted, the sender then being activated to transmit its remaining data bits. This procedure continues until all of the senders have completed the sending of their data word. In this manner, the sender having the smallest word numerically transmits the word first on the communication channel. All senders are given an opportunity to transmit their word prior to any sender sending a second word.
The '074 Pat. No. results in significant data compression because words are simultaneously transmitted from the multiple senders to the extent that their data is redundant, the non-redundant data being transmitted sequentially. Reconstruction of a complete word is subsequently performed by the receiver which appends the higher order bits to subsequently received lower order bits.
Previously, the use of serial communication links to couple distributed memories in computer architectures was limited due to the additional time required to transmit data serially. Furthermore, the choice of memory was limited to conventional RAMs or the like which operate by conventional addressing. Certain operations such as search operations are inherently slow because each RAM must cycle through every address. The serial data transmission delay is significantly reduced by the '074 patent, which increases the rate of serial communication. If the RAM accessing delay could be eliminated, a distributed computer system which utilizes modular memories connected through a serial communication link to a central processor would be a practical system with many advantages. For example, the memory capacity could be expanded or contracted (depending upon the needs of the user) simply by connecting or disconnecting memory modules to/from the serial communications link. Furthermore, although single-processor supercomputers may be prohibitively expensive, an equivalent amount of computing power could be realized by a distributed system using numerous interconnected memory modules. The smaller memories could be manufactured at a lower cost in the aggregate.